/*
题目: 不含连续 1 的非负整数
给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。

https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/
 */
public class FindIntegers {
    char[] cs = null;
    int size = 0;
    int[][] memo = null;

    public int findIntegers(int n) {
        // 先将 n 构造成 2 进制
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            sb.append(n % 2);
            n /= 2;
        }
        cs = sb.reverse().toString().toCharArray();
        size = cs.length;

        // 表示到达第 i 位的时候, 有没有连续的 1
        // 要么有连续的 1, 要么没有, 所以只有两种状态, mark : 当前位为 0 时为 0, 当前位为 1 时为 1
        memo = new int[size][2];
        for (int i = 0; i < size; i ++) {
            Arrays.fill(memo[i], -1);
        }

        return dfs(0, 0, true);
    }

    private int dfs(int pos, int mark, boolean limited) {
        if (pos >= size) {
            return 1; // 没有连续 1, mark 就是 1, 有连续 1 返回 0, 刚好不满足题意
        }

        if (!limited && memo[pos][mark] != -1) {
            return memo[pos][mark];
        }

        int src = 0;
        for (int i = 0, up = limited ? cs[pos] - '0' : 1; i <= up; i ++) {
            if (mark == 1 && i == 1) {
                continue ;
            }
            src += dfs(pos + 1, i, limited && i == up);
        }

        if (!limited) {
            memo[pos][mark] = src;
        }
        return src;
    }
}
